package hot100;

import org.junit.Test;

public class ReverseKGroup {
    public class ListNode {
        int val;
        ListNode next;

        ListNode(int x) {
            val = x;
            next = null;
        }
    }

    @Test
    public void test() {
        ListNode head = constructList(new int[]{1, 2, 3, 4, 5});
        printList(head);
        reverseKGroup(head,2);
    }

    public ListNode reverseKGroup(ListNode head, int k) {
        ListNode preHead = new ListNode(-1);
        preHead.next = head;
        ListNode p = head,pre = preHead,nextPre = null,nextStart = null;
        while (p != null) {
            //先一遍遍历找到下一组的第一个和这一组的最后一个
            int i = k;
            while (p != null && i > 0) {
                if (i == 1) nextPre = p;
                p = p.next;
                i--;
            }
            if (i > 0) break;//最后一组不需要
            nextStart = p;//不是最后一组则当前p是下一组的第一个
            ListNode leftToRight = pre.next;
            p = leftToRight;
            //头插法
            while (p != nextStart) {
                ListNode temp = p.next;
                p.next = pre.next;
                pre.next = p;
                p = temp;
            }
            nextPre = leftToRight;//下一组的前缀
            nextPre.next = nextStart;//当前组连接下一组
            pre = nextPre;
            p = nextStart;
        }

        return preHead.next;
    }

    public ListNode constructList(int[] arr) {
        ListNode preHead = new ListNode(-1);
        ListNode tail = preHead;
        for (int num : arr) {
            ListNode node = new ListNode(num);
            tail.next = node;
            tail = node;
        }

        return preHead.next;
    }

    public void printList(ListNode head) {
        ListNode p = head;
        while (p != null) {
            System.out.print(p.val + " ");
            p = p.next;
        }
    }
}
